const common = require('./base/common');

/**
 * 456. 132 模式
 * 
 * Note: 单调栈解法，构建一个单调栈，存储的每个S[i]是除N[i]以外左边序列最小元素的值。
 * 
 * @param {number[]} nums 数字数组
 * @return {boolean}
 */
 var find132pattern = function(nums) {
    let leftMin = [Infinity];

    for(let i=1; i < nums.length; ++i) {
        leftMin[i] = Math.min(leftMin[i - 1], nums[i - 1]);
    }

    let stack = [];
    for(let i=nums.length - 1; i >= 0; --i) {
        let numsk = -Infinity;
        while(stack.length > 0 && nums[i] > stack[stack.length - 1]) {
            numsk = stack.pop();
        }
        
        if(numsk > leftMin[i]) {
            return true;
        }

        stack.push(nums[i]);
    }

    return false;
};

common.testing([
    [1,2,3,4],
    [3,1,4,2],
    [3,5,0,3,4],
    [-1,3,2,0],
    [1,3,2,4,5,6,7,8,9,10]
], [false, true, true, true, true])(args => find132pattern(args));
